这个题是一个比较清晰的三分求最值的板子,在这里提供一种不太一样的三分写法。
看到题解区都是取的三等分点来三分,事实上我们只需要取中点左边偏一点点和右边偏一点点就可以了,由于题目要求的精度比较高,实际效果基本类似于二分,效率比正常三分法要稍快一些。
我在这里直接选取 和 作为左右端点,其中 为我设置的精度,在 量级。
其余过程与三分法无异,每次算出两端函数值并舍弃一边的区间,重复上述过程直至满足精度要求。
Code
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
const int N = 1e4 + 5;
const double eps = 1e-11;
int a[N], b[N], c[N], n;
inline double f(double x, int i) {
return a[i] * x * x + b[i] * x + c[i];
}
inline double check(double x) {
double ret = f(x, 1);
for (int i = 2; i <= n; i++) ret = max(ret, f(x, i));
return ret;
}
int main() {
int T; scanf("%d", &T);
while (T--) {
memset(a, 0, sizeof(a));
memset(b, 0, sizeof(b));
memset(c, 0, sizeof(c));
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d%d%d", &a[i], &b[i], &c[i]);
double l = 0, r = 1000;
while (fabs(r - l) >= eps) {
double mid = (l + r) / 2;
if (check(mid + eps) < check(mid - eps)) l = mid;
else r = mid;
}
printf("%.4lf\n", check(l));
}
return 0;
}